package sort

// sort排序算法

/*
	算法复杂度O(n^2): 冒泡、插入、选择、希尔		基于比较
	算法复杂度O(n * log(n)): 快排、归并、堆排序	基于比较
	算法复杂度O(n): 桶、计数、基数			不给予比较
*/
type Sort func(arr []int) []int

// 基数排序（Radix sort）- 针对数据可以划分为高低位，位之间有递进关系的数据
// 我们只需要比较高位，高位相同再比较低位，
// 而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。
//
// 时间复杂度：O(k * n) k为要排序的基数，当k不大时，如排序手机号，则k=11，近似于O(n)
// k代表维度
//
// 数据长度为k，按照长度位进行排序，从最小位开始排，最后排完最大位，对应位数据排序可以
// 使用桶排序或者计数排序，保证时间复杂度O(n)。最后所有位排序完毕后，整个数组也就排序完毕了。
//
// 对于数据不等长的，可以用不影响排序的字符补充成同长数据，如0或其它。
//
// 基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，
// 而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，
// 那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，
// 要可以用线性排序算法来排序，否则，基数排序的的时间复杂度就无法做到 O(n) 了。
//
// 极客时间版权所有: https://time.geekbang.org/column/article/42038。
func RadixSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	return arr
}

// 计数排序（Counting sort）- 针对数据范围相对更小的数据
// 时间复杂度：O(n + k) k是数据范围
// 空间复杂度：O(n + k) k为处理后的数据最大值
//
// 计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，
// 值所处的范围并不大（甚至非常小的时候）的时候（最大值-最小值范围较小），
// 比如最大值是 k，最小值是m，
// 我们就可以把数据划分成 k-m 个桶。
// 每个桶内的数据值都是相同的，省掉了桶内排序的时间。
//
// 计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，
// 就不适合用计数排序了。而且，计数排序只能给非负整数排序，
// 如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
//
// 计数排序: 假设数组中存储的都是非负整数
func CountingSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	// 查找数组中数据的范围 最大值
	max := arr[0]
	for i := 1; i < n; i++ {
		if max < arr[i] {
			max = arr[i]
		}
	}

	// 申请一个计数数组 c，下标大小 [0,max]
	c := make([]int, max+1)
	for i := 0; i <= max; i++ {
		c[i] = 0
	}

	// 计算每个元素的个数，放入 c 中
	for i := 0; i < n; i++ {
		c[arr[i]]++
	}

	// 依次顺序累加
	for i := 1; i <= max; i++ {
		c[i] = c[i-1] + c[i]
	}

	// 临时数组 tmpArr，存储排序之后的结果
	tmpArr := make([]int, n)
	// 计算排序的关键步骤，有点难理解
	for i := n - 1; i >= 0; i-- {
		index := c[arr[i]] - 1
		tmpArr[index] = arr[i]
		c[arr[i]]--
	}
	// 将结果拷贝给 arr 数组
	for i := 0; i < n; i++ {
		arr[i] = tmpArr[i]
	}
	return arr
}

// 桶排序（Bucket Sort） - 针对数据范围不大的数据
// 时间复杂度：最好O(n)，最坏O(n * log(n)) 平均O(n)
// 空间复杂度：O(n * k) k为桶数
//
// 按照最小最大值确定，桶数以及每个桶的数据范围（桶间是有序的），
// 对数据进行分桶，桶内部使用快排，最后将桶内数据按照桶间顺序拼接即可.
//
// 桶排序排序的元素的数据范围不能太大，不然会降低其效率，因为当数据范围过大，
// 而桶数因为无法无限而限定在一定的数量内，则每桶内的元素数量将会很大，
// 使用快排的时间复杂度影响也会越大，极端情况可能会演化为O(n * log(n)).
func BucketSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	min, max := arr[0], arr[0]
	for i := 1; i < n; i++ {
		if min > arr[i] {
			min = arr[i]
		}
		if max < arr[i] {
			max = arr[i]
		}
	}

	// 计算桶数
	bucketNum := calcBucketNum(max, min)
	// 每个桶的值范围
	difference := (max - min + 1) / bucketNum
	if difference < 1 {
		difference = 1
	}

	// 初始化bucket
	buckets := make([][]int, bucketNum)
	for i := 0; i < bucketNum; i++ {
		// 这里只是初始化，最终切片长度不一定
		buckets[i] = make([]int, 0)
	}

	// 元素分桶
	for i := 0; i < n; i++ {
		index := arr[i]/difference - min
		if index < 0 {
			index = 0
		}
		if index >= bucketNum {
			index = bucketNum - 1
		}
		buckets[index] = append(buckets[index], arr[i])
	}

	// 局部快排
	for i := 0; i < bucketNum; i++ {
		buckets[i] = QuickSort(buckets[i])
	}

	// 元素拷贝回去
	index := 0
	for i := 0; i < bucketNum; i++ {
		for j := 0; j < len(buckets[i]); j++ {
			arr[index] = buckets[i][j]
			index++
		}
	}
	return arr
}

func calcBucketNum(max int, min int) int {
	val := (max - min + 1) / 10
	if val < 10 {
		return max - min + 1
	} else if 10 <= val && val < 100 {
		return val
	} else {
		return 100
	}
}

// 快排在O(n)时间复杂度下求第K大元素
func FindNumKEleWithQuickSort(arr []int, k int) (found bool, ele int) {
	n := len(arr)
	if n < 2 {
		return false, ele
	}
	if k > n {
		return false, ele
	}

	return true, findTheK(arr, 0, n-1, k)
}

func findTheK(arr []int, p int, r int, k int) int {
	pivot := partition(arr, p, r)
	if pivot+1 == k {
		return arr[pivot]
	} else if pivot+1 < k {
		return findTheK(arr, pivot+1, r, k)
	} else {
		return findTheK(arr, p, pivot-1, k)
	}
}

// 快速排序（Quick Sort）
// 原地排序
// 非稳定排序
// 最好O(n * log(n)) 最坏O(n^2) 平均O(n * log(n))
//
// 最坏情况的考虑是，如果数组已经有序了，那么每次只会分为两个部分，而不是三个部分
// 还会需要n次分区操作，而不是log(n)次了.
func QuickSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	quickSort(arr, 0, n-1)
	return arr
}

// 局部时间复杂度 最好O(log(n)) 最坏(n) 平均O(log(n))
func quickSort(arr []int, p int, r int) {
	if p >= r {
		return
	}

	pivot := partition(arr, p, r)
	quickSort(arr, p, pivot-1)
	quickSort(arr, pivot+1, r)
}

// 时间复杂度O(n)
func partition(arr []int, p int, r int) int {
	i := p
	for j := p; j < r; j++ {
		if arr[j] < arr[r] {
			tmp := arr[j]
			arr[j] = arr[i]
			arr[i] = tmp

			i++
		}
	}
	tmp := arr[i]
	arr[i] = arr[r]
	arr[r] = tmp
	return i
}

// 归并排序
// 非原地排序
// 稳定排序
// 最好O(n * log(n)) 最坏O(n * log(n)) 平均O(n * log(n))
// 空间复杂度：O(n)
// 不是O(n * log(n))这样累加计算的原因是：在合并完成后，临时申请的空间就会被释放掉，
// 而同一时间CPU只有一个函数在执行，也只会有一个临时空间内存，临时空间内存最大为n
//
// MergeSort(arr(p...r)) = merge(MergeSort(p...q), MergeSort(q+1...r))
// 递归终止条件：p>=r
//
// 时间复杂度分析:
// T(n) = 2*T(n/2) + n
//     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
//     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
//     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
//     ......
//     = 2^k * T(n/2^k) + k * n
//     ......
//
// 通过这样一步一步分解推导，我们可以得到 T(n) = 2^k * T(n/2^k)+k * n。
// 当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2(n) 。
// 我们将 k 值代入上面的公式，得到 T(n)=C * n+n * log2(n) 。
// 如果我们用大 O 标记法来表示的话，T(n) 就等于 O(n * log(n))。
// 所以归并排序的时间复杂度是 O(n * log(n))。
func MergeSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	mergeSort(arr, 0, n-1)
	return arr
}

// 拆分的时间复杂度O(log(n))
func mergeSort(arr []int, p int, r int) {
	if p >= r {
		return
	}

	// 拆分
	mergeSort(arr, p, (p+r)/2)
	mergeSort(arr, (p+r)/2+1, r)

	// 归并并排序
	merge(arr, p, (p+r)/2, r)
}

// 合并两个部分的时间复杂度为O(n)
func merge(arr []int, p int, q int, r int) {
	// 暂存切片
	tmp := make([]int, r-p+1)

	// 两部分都有数据情况，比较并append
	i, pre, suf := 0, p, q+1
	for pre <= q && suf <= r {
		// 这里优先放入前半部分数据，保证稳定排序
		if arr[pre] <= arr[suf] {
			tmp[i] = arr[pre]
			i++
			pre++
		} else {
			tmp[i] = arr[suf]
			i++
			suf++
		}
	}

	// 有一部分全部已加入到tmp中，
	// 另一部分剩下的全部append
	start, end := pre, q
	if suf <= r {
		start = suf
		end = r
	}

	for start <= end {
		tmp[i] = arr[start]
		i++
		start++
	}

	// 排好序的tmp复制回原切片
	for i, j := 0, p; i < len(tmp); {
		arr[j] = tmp[i]
		j++
		i++
	}
}

// 选择排序（Selection Sort）
// 分为已排序区间和未排序区间，按照比较顺序选择未排序区间最小的元素append到已排序区间
// 原地排序
// 不稳定排序：会将比较顺序相同的两个值交换顺序位置
// 最好O(n^2) 最坏O(n^2) 平均O(n^2)
// @param arr 切片
func SelectionSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	for i := 0; i < n-1; i++ {
		minIndex := i
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		if minIndex != i {
			tmp := arr[minIndex]
			arr[minIndex] = arr[i]
			arr[i] = tmp
		}
	}
	return arr
}

// 插入排序（Insertion Sort）
// 分为已排序区间和未排序区间，将未排序区间元素按照比较顺序插入到已排序区间
// 原地排序
// 稳定排序
// 最好O(n) 最坏O(n^2) 平均O(n^2)
// @param arr 切片
func InsertionSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	for i := 1; i < n; i++ {
		value := arr[i]
		j := i - 1
		for ; j >= 0; j-- {
			if arr[j] > value {
				// 已排序区间最后一个元素比待插入元素大，则将该元素后移
				// 上边的value := arr[i] 保证了带插入值被保存下来，不会丢失
				arr[j+1] = arr[j]
			} else {
				break
			}
		}
		// 插入数据
		arr[j+1] = value
	}
	return arr
}

// 希尔排序（Shell Sort）插入排序的优化版本
// 以指定步长将大数组分隔为小数组，排序小数组同一index角标位置元素。
// 然后以指定算法缩小步长，最后步长为1，在进行一次基本的插入排序
// 得到最后排好序的数组。
//
// 在小数据量时，可能比快排和堆排序块，但是大数据量上不如
// 算法复杂度
// 最好 O(n * log(n))
// 最坏 O(n * log(n^2)) => O(2n * log(n))
// 平均 O(n * log(n^2)) => O(2n * log(n))
//
// 比较好的理解方式见维基: https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
func ShellSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	for step := n / 2; step > 0; step = step / 2 {
		for i := step; i < n; i = i + step {
			value := arr[i]
			j := i - step

			for ; j >= 0; j = j - step {
				if arr[j] > value {
					arr[j+step] = arr[j]
				} else {
					break
				}
			}
			arr[j+step] = value
		}
	}

	return arr
}

// 冒泡排序（Bubble Sort）
// 相邻元素冒泡向后迭代按照比较顺序交换，每次倒数第i位元素都被确定
// 原地排序
// 稳定排序
// 最好O(n) 最坏O(n^2) 平均O(n^2)
// @param arr 切片
func BubbleSort(arr []int) []int {
	n := len(arr)
	if n < 2 {
		return arr
	}

	for i := 0; i < n; i++ {
		hasSwap := false
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				hasSwap = true
				tmp := arr[j+1]
				arr[j+1] = arr[j]
				arr[j] = tmp
			}
		}

		if !hasSwap {
			break
		}
	}
	return arr
}
